/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package chulbulpandeyproblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

/**
 *
 * @author nikhil
 */
public class UserMainCode {

    public static int[] output1;
    public static int policeCount;
    public static int stationCount;
    public static int[] policeCapability;
    public static int[] policePerStationSet;
    public static ArrayList<Station> StationSet;
    public static Station[] stationset = null;

    public static void BalanceCapability(int policeCount, int stationCount, int[] policeCapability) {
        UserMainCode.policeCount = policeCount;
        UserMainCode.stationCount = stationCount;
        Arrays.sort(policeCapability);
        UserMainCode.policeCapability = policeCapability;
        int averagePolicePerStation = policeCount / stationCount;
        policePerStationSet = new int[stationCount];
        StationSet = new ArrayList<Station>();
        arrangePolicePerStation(averagePolicePerStation);
        createBalancedSets();
        balancingStationCapability();
        output1 = new int[stationCount];
        for(int i=0;i<stationCount;i++)
            output1[i]= stationset[i].policeCapability;
       //showOuput();
    }

    private static void arrangePolicePerStation(int averagePolicePerStation) {
        int counter = UserMainCode.stationCount - 1;
        int sum = 0;
        for (int i = 0; i < stationCount; i++) {
            policePerStationSet[i] = averagePolicePerStation;
            sum += policePerStationSet[i];
        }
        while (sum != UserMainCode.policeCount) {
            policePerStationSet[counter]++;
            counter--;
            sum++;
        }

    }

    private static void showOuput() {
        for (int i : policePerStationSet) {
            System.out.print(i + "\t");
        }
        
        System.out.println();
        System.out.println();
        
        for (int i : output1) {
            System.out.println(i+"\t");
        }
        
    }

    private static void createBalancedSets() {
        for (int i : policePerStationSet) {
            Station station = new Station();
            station.numberOfPolice = i;
            StationSet.add(station);
        }
    }

    private static void balancingStationCapability() {
        int min = 0;
        int max = policeCapability.length;

        boolean[] flags = new boolean[max];
        for (int i = 0; i < max; i++) {
            flags[i] = false;

            //  Setting Up First Phase

            Iterator iterator = StationSet.iterator();
            while (iterator.hasNext()) {
                Station station = (Station) iterator.next();
                station.policeCapability = policeCapability[min] + policeCapability[max-1];
                station.capabilityAdded = 2;
                flags[min] =true;
                flags[max-1] = true;
                min++;
                max--;
            }

            stationset = new Station[StationSet.size()];
            StationSet.toArray(stationset);
            int counter = 0;
            for (i = 0; i < max; i++) {
                if (flags[i] == false) {
                    counter = searchSmallestCapability();
                    stationset[counter].policeCapability +=policeCapability[i];
                    flags[i]=true;
                    stationset[counter].capabilityAdded++;
                    updateStatus();
                }
            }
        }
    }

    private static int searchSmallestCapability() {
        Station station = stationset[0];
        int counter = 0;
        for (int i = 0; i < stationset.length; i++) {
            if (stationset[i].policeCapability < station.policeCapability && !stationset[i].status) {
                station = stationset[i];
                counter = i;
            }
        }
        return counter;
    }

    private static void updateStatus() {
        for (int i = 0; i < stationset.length; i++) {
            if (stationset[i].capabilityAdded == stationset[i].numberOfPolice) {
                stationset[i].status = true;
            }
        }
    }
    static class Station {

    int numberOfPolice=0;
    int policeCapability=0;
    int capabilityAdded=0;
    boolean status;   //true for Capability Complete
}
}

